package com.zrf.base.knowledge.leetcode.editor.cn;

/**
 * //给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * //
 * // 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * //
 * // 你可以假设 nums1 和 nums2 不会同时为空。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * // nums1 = [1, 3]
 * //nums2 = [2]
 * //
 * //则中位数是 2.0
 * //
 * //
 * // 示例 2:
 * //
 * // nums1 = [1, 2]
 * //nums2 = [3, 4]
 * //
 * //则中位数是 (2 + 3)/2 = 2.5
 * //
 * // Related Topics 数组 二分查找 分治算法
 * // 👍 3195 👎 0
 *
 * @author zhouruifeng
 * @date 2020-09-17 22:40:34
 */
public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();
        int[] num1 = new int[]{1, 2, 3, 6, 7};
        int[] num2 = new int[]{5, 8, 9, 10};
        solution.findMedianSortedArrays(num1, num2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int start1 = -1;
            int start2 = -1;

            int totalLength = nums1.length + nums2.length;
            int middle = (totalLength + 1) / 2;
            int middleValue = 0;

            while (start1 + start2 < middle) {
                int num1 = nums1[start1  + (nums1.length - start1 - 1) / 2];
                int num2 = nums2[start2  + (nums2.length - start2 - 1) / 2];
                if (num1 < num2) {
                    start1 = start1 + (nums1.length - start1 - 1) / 2;
                } else {
                    start2 = start2  + (nums2.length - start2 - 1) / 2;
                }
            }

            System.out.println(nums1[start1]);
            System.out.println(nums2[start2]);
            return 0d;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}